//给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度
//。如果气温在这之后都不会升高，请在该位置用 0 来代替。 
//
// 
//
// 示例 1: 
//
// 
//输入: temperatures = [73,74,75,71,69,72,76,73]
//输出: [1,1,4,2,1,1,0,0]
// 
//
// 示例 2: 
//
// 
//输入: temperatures = [30,40,50,60]
//输出: [1,1,1,0]
// 
//
// 示例 3: 
//
// 
//输入: temperatures = [30,60,90]
//输出: [1,1,0] 
//
// 
//
// 提示： 
//
// 
// 1 <= temperatures.length <= 10⁵ 
// 30 <= temperatures[i] <= 100 
// 
// Related Topics 栈 数组 单调栈 👍 1143 👎 0

package leetcode.editor.cn;

import java.util.Stack;

class DailyTemperatures {
    public static void main(String[] args) {
        Solution solution = new DailyTemperatures().new Solution();
        solution.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 详细解析
         * 情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
         * 情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
         * 情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
         *
         * @param temperatures
         * @return
         */
//        public int[] dailyTemperatures(int[] temperatures) {
//            // 递增栈，栈顶到栈底时从小到大
//            Stack<Integer> stack = new Stack<>();   // 栈中存储的是数组下标
//            int[] res = new int[temperatures.length];  // 记录结果的数组
//            stack.push(0);  // 将第一个下标放入
//
//            for (int i = 1; i < temperatures.length; i++) {
//                // 如果小于直接入栈
//                if (temperatures[i] < temperatures[stack.peek()]) {
//                    stack.push(i);
//                }
//                // 等于也入栈，此时依然要加入栈，不用计算距离，因为我们要求的是右面第一个大于本元素的位置，而不是大于等于！
//                else if (temperatures[i] == temperatures[stack.peek()]) {
//                    stack.push(i);
//                }
//                // 大于直接入栈
//                else if (temperatures[i] > temperatures[stack.peek()]) {
//                    // 将小于入栈数的都出栈，然后在将栈顶减去下标就是右边第一个比自己大的元素
//                    while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
//                        res[stack.peek()] = i - stack.peek();
//                        stack.pop();
//                    }
//                    stack.push(i);
//                }
//            }
//
//            return res;   // 最终栈里存在的元素表示右边没有比它更大的值，所以初始化结果数组时都是0
//        }

        /**
         * 简化版
         *
         * @param temperatures
         * @return
         */
        public int[] dailyTemperatures(int[] temperatures) {
            // 递增栈，栈顶到栈底时从小到大
            Stack<Integer> stack = new Stack<>();   // 栈中存储的是数组下标
            int[] res = new int[temperatures.length];  // 记录结果的数组
            stack.push(0);  // 将第一个下标放入

            for (int i = 1; i < temperatures.length; i++) {
                while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                    res[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
